// 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列
// （即，组合出下一个更大的整数）。
// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
// 必须 原地 修改，只允许使用额外常数空间。

// 示例 1：
// 输入：nums = [1,2,3]
// 输出：[1,3,2]

// 示例 2：
// 输入：nums = [3,2,1]
// 输出：[1,2,3]

// 示例 3：
// 输入：nums = [1,1,5]
// 输出：[1,5,1]

// 示例 4：
// 输入：nums = [1]
// 输出：[1]

// 提示：
//     1 <= nums.length <= 100
//     0 <= nums[i] <= 100

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
////[1, 5, 2, 4, 3, 2]
var nextPermutation = function(nums) {
    let i = nums.length - 2;
    while(i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while(j >= 0 && nums[j] <= nums[i]) { ///从后面寻找比num[i]第一个大的数   交换
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    ///注意：此刻还不是下一个更大的数，可能比下一个更大的数要大，因为i的右边可能是递减的，需要换成递增的
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {                            // i 右边的数进行翻转，使得变大的幅度小一些
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l++;
        r--;
    }
    return nums;
};

console.log(nextPermutation([1,1,5]));


